package q1535_getWinner;

import java.util.Arrays;

public class Solution {
    /*
    首先明确几个特殊情况：k = 1或者arr长度为2 可以直接得到答案
    如果k >= arr.length - 1 那么显然比较的数字数量超过了数组的长度 最后一定选出的是数组的最大值
    除此之外维护一个idx和prev 不需要交换数组中的数字 依次比较即可
     */
    public int getWinner(int[] arr, int k) {
        if (k == 1 || arr.length == 2) return Math.max(arr[0], arr[1]);
        if (k >= arr.length - 1) return Arrays.stream(arr).max().getAsInt();
        int count = 1, maxVal = Math.max(arr[0], arr[1]), idx = 1, prev = maxVal;
        while (idx < arr.length && count < k) {
            maxVal = Math.max(maxVal, arr[idx + 1]);
            if (maxVal == prev) {
                ++count;
            } else {
                count = 0;
                prev = maxVal;
            }
            ++idx;
        }
        return maxVal;
    }
}
